3Algorithm Building Blocks 算法构建块

我们构建软件解决问题，但编程通常不可能找到现成代码解决特定问题。因此了解算法，根据问题找到算法，根据算法写出程序是很好的。

算法模板格式 Algorithm Template Format
每一个算法的所有模块都是符合这个模板的。我们会省略算法中不必要的模块，如果可以优化某个点，我们会添加这个模块。

• Name 名字
  算法的名字有描述性、简洁性
• input/output 输入输出
  描述给算法的数据的形式和输出结果的形式
• Context 应用场景
  算法的应用场景，应该保留算法的成功应用的时候的例子/特征，可以帮助你挑选算法
• Solution 解决方案
  就是代码
• Analysis 分析
  算法简要的分析，包括算法在数据量不同时的表现。（我们更应该了解算法原理，这时再解释为什么会有这样的表现）
• Variations 变种
  算法的其他变种或其他类似算法

Pseudocode Template Format 伪代码模板格式
第一行：Best:O(f(n)) Average:O(g(n)) Worst:O(h(n))
后面：几乎和 python 一样，好看懂的伪代码。
（可以在最后附上图，描绘动态计算过程。）

Empirical Evaluation Format 经验评估格式
我们用一系列基准数据判断每一个算法，一般测试集有 k 组数据（k>=10），最好和最坏情况被看作离群值，统计其余的 k-2 个数据的平均值和标准差。问题实例的规模通常在 2~2^20 不等。

Floating Point Computing 浮点计算

1. CPU 计算的是寄存器上的数据，CPU 支持的运算是 ADD，MULT，DIVIDE，SUB。
   FPUs(floating-point units) 可以根据 IEEE 的储存浮点类型的标准高效计算浮点类型的数据。

CPU 在计算整数类型的时候效率是最高的，但现在的计算机计算小数效率也非常高了，当编程人员用小数时，特别注意下面的方面。
2. Performance 表现，通常认为整数比浮点数运算快，对整数的运算有时会快到没法计时。
3. Rounding Error 舍入误差
缘于浮点数的存储方式，所有浮点计算都有可能引起误差。总的来说，浮点数就是用一个有限的数代表真实的小数 (有可能无限)

对一个四字节的浮点数，共 32 位，1 位表示符号，8 位表示指数，23 位表示尾数。

java 对浮点数的说明：the power of two can be determined by interpreting the exponent bits as a positive number, and then subtracting a bias from the positive number. For a float, the bias is 126 二的幂可以通过将指数位解释为正数，然后从正数中减去偏差来确定。对于浮点数，偏差为 126。又因为储存的指数为是 128，所以实际的指数是 128-126=2

为了精度高，尾数总是被标准化，因此最左面的数字总是 1，它即使不必被存储，但浮点处理器需要识别它。

通常描述浮点的误差，使用相对误差，计算绝对误差和期望值的比。一般 float 误差小于百万分之一。
4. Comparing Floating-Point Values 比较浮点的值
由于浮点数是个估计值，那么最简单的比较对于浮点数来说就值得怀疑了。

平面的三个点构成两个线段，我们判断三点是否共线，只需要考虑两个线段的斜率是否一样。但由于浮点计算，会导致一点点误差，两个线段斜率不同了！

通常，解决方法是引入一个δ去描述两个浮点数的约等于关系。如果|x-y|<δ，我们就说他们相等（但这样的约等于不具有传递性 x=y，y=z 可知 x=z，但换成约等于就不行）。总的来说共线问题不算完全解决了。
5. Special Quantities 特殊数量
IEEE 标准定义了一些特殊的数字。这些数字通常不能参与标准的计算（加和乘），可以更方便的返回一些普通错误，比如除以 0，负数开方，数字溢出，数字下溢 (underflow of computations) 等。正 0 和负 0 都被包括在了里面，虽然它们可以在计算中被使用。

如果 java 计算 1/0.0，会得到正无穷，如果改成 double x=1/0，java 会报错，因为它计算的是两个整数的除法。

Example Algorithm 算法例子

1. Name and Synopsis 名字
   Graham's Scan 计算凸包问题的算法。

先定位最低点，当作极点，建立极轴，之后按极角大小，为剩下的点排序。算法会从最低点沿顺时针方向画出凸包。

每次出现左转情况的时候，说明相邻的三个点出现了凹陷，此时我们去除中间凹陷的那个点，再继续判断。

2. Input/Output 输入输出
   输入：一个平面点集

输出：一个凸包的点集（不论顺序）

3. Context 应用场景
   笛卡尔系的一些点，寻找凸包。

4. Solution 实例代码
   java 代码我敲在电脑里了。

我网上查到的 python 代码记录在电脑里了。

（如果所有点共线的话，算出来的凸包会有连续的共线点，因为没有扔掉他们）

5. Analysis 分析
   给 n 个点排序的时间复杂度是 O(nlogn)，剩余的 for 循环执行 n 次，内部的 while 执行次数一共不超过 n 次，因此 for 循环的时间复杂度是 O(n)。排序占了整个算法的绝大部分时间。

6. 总结
   Graham's Scan Summary

Best,Average,Worst:O(nlogn)

Graham(P)

low = point with lowest y coordinate in P

remove low from p

sort P by descending polar angle with respect to low

hull={p[n-2],low}

for i=0 to n-1 do

while (isLeftTuen(secondLast(hull), last(hull), p[i])) do

remove last point in hull

add p[i] to hull

remove duplicate last point

return hull

注意：P[0] 角度最大，P[n-2] 角度最小。搜索从逆时针最小角和最低点开始。

Common Approaches 常用方法
这里介绍了书中用到的基本的算法，这些大体上的思想会被应用于不同的，具体的问题。

1. Greedy 贪心算法
   算法分为几步，每一步取本步的最优，每一步求完后就组成了全局最优。

如果子问题的时间复杂度比较小，这样的算法就是可以考虑的。（注意局部最优不一定组成全局最优）
2. Divide and Conquer 分治法
将一个规模为 n 的问题分解为两个独立的小问题，通常通过递归解决，通常将小问题组合起来也需要一些运算。

例子：一堆数找最大的一个

分治后，算法总时间分为每个子问题的计算时间、组合子问题需要的时间两部分。这也是为什么分治法不是总可以提供最快的解法。
3. Dynamic Programming 动态规划
是分治法的一种变体，将问题划分为一系列具有顺序的子问题。解决子问题的时候存储结果，以便后期使用。许多情况下可以得到最优的解决方案。

动态规划技巧是，优化循环，考虑如何让循环的小问题的结果用于解决大一些的问题。

动态规划经常被用于优化类问题，目标是寻找最小或者最大的东西。

• 实例问题
  科学家经常比较 DNA 序列以确定他们的相似点。如果将 DNA 表现为一串字符 ACTG，现在给你 s1 和 s2 两串字母序列，请计算最少编辑多少次，可以让两个序列相同。

你的编辑方式有，

在 s1 中用另一个字母替换该字母；

去除 s1 的某个字母；

插入某个字母到 s1 里。

• 解答
  问题分析：

我们不需要计算方法，只需要计算次数。

解决方法：

创建一个矩阵储存子问题的结果，m[i][j] 记录 s1 的前 i 个字母和 s2 的前 j 个字母相同的最少编辑次数。（比如 m[0][4]=4，因为 s1 前 0 个是空字符串，s2 前 4 个是某四个字母，因此要在 s1 插入 4 个字母。）

问题的关键在于识别出，m[i][j] 这个单元格的值可以从它左、上、左上三个单元格得出，

从左侧得出，则 m[i][j] 值为左侧单元格加一，代表 s1 移除了一个；

从上面得出，则 m[i][j] 值为上方单元格加一，代表 s1 增加了一个；

从左上方得出，代表更换了一个，如果最后一个字母相同的话，则两个格子值相同，如果最后一个字母不同，则值为左上方格子加一。

代码实现：

python 代码，打到电脑里了。